#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE            1
#define FALSE           0

#define HEAD            "int"
#define TAIL            "OrzZhd32"
#define EQUAL           '='
#define TOKEN           ","

#define SIZE(s)         (sizeof(s)-1)
#define SIZE_ARRAY(a)   (sizeof(a)/sizeof(a[0]))

#define MAXNODES        8192

typedef int (*check_func)(const char *, int);

struct node 
{
    int symbol;
    struct node *first;
    struct node *next;
    void *data;
};

struct node root;

/* add a node with keyword, the last keyword node store the data */
void add_node(struct node *root, const char *keyword, void *data)
{
    int i, len;
    struct node *p, *f, *r, *newnode, *lastnode;

    if (root == NULL || keyword == NULL || (len = strlen(keyword)) <= 0)
        return ;

    i = 0;
    p = root->first;
    f = root;
    r = NULL;
    while (p != NULL && i < len)
    {
        if (p->symbol == keyword[i])
        {
            f = p;
            p = p->first;
            i ++;
            r = NULL;
        }
        else if (p->symbol < keyword[i])
        {
            r = p;
            p = p->next;
        }
        else 
            break;
    }

    if (f != NULL && i == len)
    {
        f->data = data;
        return ;
    }

    lastnode = malloc(sizeof(struct node)); 
    lastnode->symbol = keyword[len-1];
    lastnode->first = NULL;
    lastnode->next = NULL;
    lastnode->data = data;

    while (len-1 > i)
    {
        newnode = malloc(sizeof(struct node));
        newnode->symbol = keyword[len-2];
        newnode->first = lastnode;
        newnode->next = NULL;
        newnode->data = NULL;
        lastnode = newnode;
        len --;
    }

    lastnode->next = p;
    if (f->first == NULL || f->first->symbol > lastnode->symbol)
        f->first = lastnode;
    if (r != NULL)
        r->next = lastnode;
}

/* 
 * search the keyword node from the str, when a node data is not null,
 * return it and the length 
 */
struct node *search_node(struct node *root, const char *str, int *len)
{
    int i;
    struct node *p;
    
    if (root == NULL || str == NULL)
        return NULL;

    i = 0;
    p = root->first;
    while (p != NULL)
    {
        if (p->symbol == str[i])
        {
            if (p->data != NULL) {
                *len = i+1; 
                return p;
            }

            p = p->first;
            i ++;
        }
        else if (p->symbol < str[i])
            p = p->next;
        else
            return NULL;
    }

    return NULL;
}

void free_nodes(struct node *root)
{
    int i = 0;
    struct node *nodes[MAXNODES], *p;
    
    nodes[i++] = root->first;
    while (i > 0)
    {
        p = nodes[--i];
        if (p == NULL)
            break;
        if (p->first != NULL)
            nodes[i++] = p->first;
        if (p->next != NULL)
            nodes[i++] = p->next;
        free(p);
    }
}

/* add a new keyword with its check function */
void add_keyword(const char *keyword, check_func func)
{
    add_node(&root, keyword, func);
}

/* 
 * check the head and get the size 
 * totalsize - size include the head and the size character
 */
static int head_size_check(const char *str, int *size, int *totalsize)
{
    int i, num;

    /* check head */
    if (strncmp(str, HEAD, SIZE(HEAD)) != 0)
    {
        printf("check %s error\n", HEAD);
        return FALSE;
    }

    /* get size */
    i = SIZE(HEAD);
    num = 0;
    while (isdigit(str[i]))
        num = num * 10 + str[i++] - '0'; 
    *size = num;

    /* get totalsize */
    *totalsize = *size + SIZE(HEAD) + i - SIZE(HEAD);

    return TRUE;
}

/* check the name */
static int name_check( const char *str, int size)
{
    return TRUE;
}

/* check the string is consist of number */
static int number_check(const char *number, int size)
{
    int i;

    i = 0;
    while (i < size && isdigit(number[i++])) ;

    if (i < size)
    {
        printf("check number error\n");
        return FALSE;
    }
    return TRUE;

    /* 
     * to do ... 
     * we can parse the number here 
     */
}

/* check the value of the keyword */
static int value_check(const char *value, int size)
{
    if (value[0] != EQUAL)
    {
        printf("check '%c' error\n", EQUAL);
        return FALSE;
    }

    /* check value, must be number? */
    if (number_check(value+1, size-1) == FALSE)
        return FALSE;
    return TRUE;
}

/* check the list of the keyword */
static int list_check(const char *list, int size)
{
    char *str, *token;

    if (list[0] != EQUAL)
    {
        printf("check '%c' error\n", EQUAL);
        return FALSE;
    }

    str = malloc(size);
    strncpy(str, list+1, size-1);
    str[size-1] = '\0';

    token = strtok(str, TOKEN);
    if (token == NULL)
    {
        printf("check list number error\n");
        free(str);
        return FALSE;
    }

    while (token != NULL)
    {
        if (number_check(token, strlen(token)) == FALSE)
        {
            free(str);
            return FALSE;
        }
        token = strtok(NULL, TOKEN);
    }

    free(str);
    return TRUE;
}

/* check the body of the string */
static int body_check(const char *str, int size)
{
    int i, strsize;
    struct node *p;

    p = search_node(&root, str, &strsize);
    if (p == NULL)
    {
        printf("check keyword error\n");
        return FALSE;
    }
    else
        return ((check_func)p->data)(str+strsize, size-strsize);
}

int validity_check(const char *request)
{
    int i, size, totalsize, subtotalsize;
    const char *tailstring;

    if (request == NULL)
    {
        printf("request string is NULL\n");    
        return FALSE;
    }

    /* check head and get size */
    if (head_size_check(request, &size, &totalsize) == FALSE)
        return FALSE;

    /* check totalsize */
    if (*(request+totalsize) != '\0')
    {
        printf("check total size error\n");
        return FALSE;
    }

    /* check tail string */
    tailstring = request + totalsize - SIZE(TAIL);
    if (strcmp(tailstring, TAIL))
    {
        printf("check %s error or total size error\n", TAIL);
        return FALSE;
    }
    
    /* check sub string */
    i = totalsize - size;
    subtotalsize = 0;
    while ((request + i) != tailstring && i < totalsize - SIZE(TAIL))
    {
        int tmpsize, tmptotalsize;

        if (head_size_check(request+i, &tmpsize, &tmptotalsize) == FALSE)
        {
            printf("check error at index %d\n", i);
            return FALSE;
        }

        i += tmptotalsize - tmpsize;
        if (body_check(request+i, tmpsize) == FALSE)
        {
            printf("check body error at index %d\n", i);
            return FALSE;
        }

        subtotalsize += tmptotalsize;
        i += tmpsize;
    }

    if (i != totalsize - SIZE(TAIL) || request+i != tailstring)
        return FALSE;

    /* check size */
    if (size != subtotalsize + SIZE(TAIL))
    {
        printf("check size error\n");
        return FALSE;
    }
    
    return TRUE;
}

int main(int argc, char const* argv[])
{
    int i;
    char *str;
    char *name_keywords[]   =   {"OrzNino", "stONino", "NinoNB", "NinoMMPP"};
    char *value_keywords[]  =   {"OrzJust", "stOJust", "JustNB", "JustMMPP"};
    char *list_keywords[]   =   {"OrzPl", "stOPl", "PlNB"};

    for (i = 0; i < SIZE_ARRAY(name_keywords); i++)
        add_keyword(name_keywords[i], name_check);

    for (i = 0; i < SIZE_ARRAY(value_keywords); i++)
        add_keyword(value_keywords[i], value_check);

    for (i = 0; i < SIZE_ARRAY(list_keywords); i++)
        add_keyword(list_keywords[i], list_check);

    printf("\n");
    
    str = "int19int7OrzNinoOrzZhd32";
    printf("%s is %s\n\n", str, validity_check(str)?"GOOD":"WRONG");
    
    str = "int20int8JustNB=9OrzZhd32";
    printf("%s is %s\n\n", str, validity_check(str)?"GOOD":"WRONG");

    str = "int33int8JustNB=8int9stOPl=1,9OrzZhd32";
    printf("%s is %s\n\n", str, validity_check(str)?"GOOD":"WRONG");

    str = "int87int7OrzNinoint7stONinoint12OrzJust=8888int11JustMMPP=00int9OrzPl=1,2int7stOPl=1OrzZhd32";
    printf("%s is %s\n\n", str, validity_check(str)?"GOOD":"WRONG");

    str = "int82int7OrzNinoint7stONinoint12OrzJust=8888JustMMPP=00int9OrzPl=1,2int7stOPl=1OrzZhd32";
    printf("%s is %s\n\n", str, validity_check(str)?"GOOD":"WRONG");

    str = "int82int7OrzNinoint7stONinoint12OrzJust=8888JustMMPP=00int9OrzPl=1,2int7stOPl=1OrzZhd";
    printf("%s is %s\n\n", str, validity_check(str)?"GOOD":"WRONG");
    
    str = "int74int7OrzNinoint7stONinoint12OrzJust=8888JustMMPP=00int9OrzPl=1,2int7stOPl=1";
    printf("%s is %s\n\n", str, validity_check(str)?"GOOD":"WRONG");

    str = "int999init6NinoNBOrzZhd32";
    printf("%s is %s\n\n", str, validity_check(str)?"GOOD":"WRONG");
    
    free_nodes(&root);
    return 0;
}


